/*
day227
2020.4.11
*/
#include<iostream>
#include<cstdlib>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct Node{
	bool isbalance=false;
	int height=0;
};

class Solution {
public:
    bool isBalanced(TreeNode* root) {
		return help(root).isbalance;
    }
    
    Node help(TreeNode* root)
    {
    	Node res;
    	if(!root)
    	{
    		res.height=0;
    		res.isbalance=true;
    		return res;
		}
		
		Node l=help(root->left);
		Node r=help(root->right);
		
		if(!l.isbalance || !r.isbalance || abs(l.height-r.height)>1)
		{
			res.isbalance=false;
			res.height=0;
			return res;
		}
		
		res.isbalance=true;
		res.height=max(l.height,r.height)+1;
		return res;
	}
};

int main()
{
	return 0;
}
